#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// 函数声明
void insertNode(Node **root, int data);
void preOrderTraversal(Node *root);
void freeTree(Node *root);

int main() {
    Node *root = NULL;  // 初始化二叉树的根节点指针为NULL，表示空树
    int inputData;
    printf("请输入一组非零整数，以0结束输入：\n");
    while (1) {
        scanf("%d", &inputData);
        if (inputData == 0) {
            break;
        }
        insertNode(&root, inputData);  // 传入根节点指针的地址（二重指针）进行节点插入操作
    }
    // 先序遍历二叉排序树并输出节点值
    printf("先序遍历二叉排序树的结果：\n");
    preOrderTraversal(root);
    printf("\n");
    // 释放二叉排序树占用的内存空间
    freeTree(root);
    return 0;
}

// 创建新的二叉树节点
Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点到二叉排序树的函数（使用二重指针）
void insertNode(Node **root, int data) {
    if (*root == NULL) {
        // 通过二重指针修改外部传入的指针的值，使其指向新创建的节点
        *root = createNode(data);
        return;
    }
    if (data < (*root)->data) {
        insertNode(&((*root)->left), data);  // 递归插入左子树
    } else {
        insertNode(&((*root)->right), data);  // 递归插入右子树
    }
}

// 先序遍历二叉树的函数
void preOrderTraversal(Node *root) {
    if (root!= NULL) {
        printf("%d ", root->data);  // 先输出当前节点值
        preOrderTraversal(root->left);  // 遍历左子树
        preOrderTraversal(root->right);  // 遍历右子树
    }
}

// 释放二叉树内存的函数
void freeTree(Node *root) {
    if (root!= NULL) {
        freeTree(root->left);  // 先释放左子树内存
        freeTree(root->right);  // 再释放右子树内存
        free(root);  // 最后释放当前节点内存
    }
}